这篇主要讲述一下关于Java 集合基础的一些内容，同时查漏补缺，完善一下自己对于集合的认识。

一、基础概念

Java 集合的使用在项目中是大量使用到的，常用的集合类大部分都是 List、Set、Map 的子类；

成员之间的一个类关系：

在我们实际接触 Java 的时候，可能第一次使用的集合是 List 下 的 ArrayList ，我们作为一个动态数组去使用它。

实际上，在类关系谱上，List 接口是有一个父接口的，即 Collection 接口； Collection 是所有单列集合类的根接口（不包括 Map，Map 是键值对集合）

在 Collection 这个根接口下，有两个主要的子接口，分别是 List 和 Set。还有一个特殊用途集合，Queue 接口及其子类。

另外还有映射接口 Map 接口及其下的实现类。

并发情况下，可以考虑使用java.util.concurrent包下的类（并发集合）

二、Collection

在介绍具体的集合实现类之前，我们先了解一下 Collection 这个顶层接口。

介绍如下：

Collection接口：最基本的集合接口，所代表的是一种规则，它所包含的元素都必须遵循一条或者多条规则。如有些允许重复而有些则不能重复、有些必须要按照顺序插入而有些则是散列，有些支持排序但是有些则不支持。

在Java中所有实现了Collection接口的类都必须提供两套标准的构造函数，一个是无参，用于创建一个空的Collection，一个是带有Collection参数的有参构造函数，用于创建一个新的Collection，这个新的Collection与传入进来的Collection具备相同的元素。

与 Collection 接口区别的一个常用关键字是 Collections ，Collections 是集合下面的一个常用工具类，提供了一些静态方法用于操作集合，比如排序、搜索、线程安全化等方法。

总结：

Collection接口 是 所有单列集合类的根接口，定义了对集合进行基本操作（如添加、删除、清空等）的方法

在这个根接口下，有两个主要子接口：List和Set。

三、List

List 接口下面的集合一般是指有序的 Collection 数据，使用某种特定的插入顺序来维护元素顺序；

元素能够通过索引进行访问，并且允许重复元素。

实现List接口的常用集合类主要有：ArrayList、LinkedList、Vector、Stack等。

小结

List 接口的特点有：

• 1、 有序的集合，其中的集合元素是可以重复的，并且元素是可以通过集合的索引下标位置进行访问的；
• 2、插入和删除是可以精确进行操作的（根据索引下标）
• 3、主要实现类包括：ArrayList、LinkedList 等。

关于 List 接口下的实现类

• ArrayList：基于动态数组实现，支持随机访问元素，适用于频繁的查找操作。
• LinkedList：基于双向链表实现，优于ArrayList进行插入、删除操作，但随机访问速度相对较慢。

ArrayList

ArrayList 是 Java 集合框架中的一部分，属于 List 接口的一个实现。它是基于动态数组的数据结构，提供了快速的随机访问能力。

ArrayList 的底层数据结构是动态数组，由于是动态数组，比较适合查询操作，对于插入、删除操作不太友好，并且 ArrayList 属于是线程不安全的集合。

ArrayList 的迭代器在遍历时，如果发现集合被修改，则会立即抛出如果发生异常，会进行抛出 并发修改异常 ConcurrentModificationException。

特点总结

• 1、底层是动态数组，支持快速随机访问（根据索引访问元素，通过索引直接访问元素的时间复杂度为 O(1)）
• 2、对于插入、删除操作不太友好；不过尾部成员的插入、删除操作影响不大，性能较好（不用数组的复制和移动）
• 3、元素可重复，有序（保持元素插入的顺序），成员可为任意 Object 子类的对象。
• 4、线程不安全
• 5、默认初始容量是10，扩容的时候会新增一个原集合容量大小的1.5倍的数组，并复制原数组到一个这个新的更大的数组中，这个操作的时间复杂度为 O(n) 【建议在添加大量元素前最好通过构造函数指定初始容量，以减少扩容次数。】

---

常用方法

• add(E e): 向列表尾部添加一个元素。
• add(int index, E element): 在指定位置插入一个元素。
• get(int index): 返回指定索引处的元素。
• remove(int index): 移除指定索引处的元素。
• set(int index, E element): 替换指定索引处的元素。
• size(): 返回列表中的元素数量。
• clear(): 移除列表中所有元素。
• isEmpty(): 判断列表是否为空。
• indexOf(Object o): 返回指定元素首次出现的索引。
• lastIndexOf(Object o): 返回指定元素最后一次出现的索引。

使用示例

List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");

System.out.println(list.get(0)); // 输出 Java

list.add(1, "JavaScript");
System.out.println(list); // 输出 [Java, JavaScript, Python, C++]

list.remove("C++");
System.out.println(list); // 输出 [Java, JavaScript, Python]

System.out.println(list.size()); // 输出 3

---

关于 ArrayList 集合一些注意的地方

插入和删除是可以精确进行操作的（根据索引下标）

在 ArrayList 中，元素是可以指定索引位置进行插入和删除的；

示例：

List<String> list = new ArrayList<>();
list.add("Element 1");
list.add("Element 2");
list.add("Element 3");
//新增操作
list.add(1, "New Element"); // 在索引1的位置新增一个元素
//这时`list`中的元素为`["Element 1", "New Element", "Element 2", "Element 3"]`。

//删除操作示例
list.remove(2); // 删除索引为2的元素（"Element 2"）

注意事项：当使用索引进行操作时，必须确保索引值在合理的范围内（0到list.size()-1），否则会抛出IndexOutOfBoundsException

当在List集合的指定索引位置使用add(int index, E element)方法插入一个新元素时，如果该位置已经有数据元素，那么原有的元素以及其后的所有元素都会向后移动一个位置（索引值增加1），以空出位置给新插入的元素。

这意味着，新元素会被插入到指定的索引位置，而原来位于该位置的元素以及所有后续元素的索引都会递增。这个操作不会替换或删除原来的元素，而是将所有元素向后推移以保留所有数据。

同理，删除操作也类似，从List中删除一个指定索引位置的元素时，位于该位置之后的所有元素都会向前移动一个位置（索引值减少1），以填补被删除元素留下的空位。

插入操作可能会影响性能，特别是对于大型列表或特定类型的List实现（如ArrayList），因为它可能涉及到数组的复制和移动。

由于这个原因，ArrayList 对于插入、删除操作不太友好；

考虑到这个原因，在特定情况下（如频繁的插入和删除），可能需要考虑其他类型的集合，如 LinkedList。

数组

ArrayList 的底层数据结构是动态数组，这里讲述一下数组相关的一些内容。

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

数组如何获取其他元素的地址值。

寻址公式：a[i] = baseAddress + i * dataTypeSize

• baseAddress:数组的首地址
• dataTypeSize：代办数组中元素类型的大小

为什么数组索引从 0 开始呢，假如从 1 开始不行吗？

参考答案：

操作数组的时间复杂度（查找）

• 索引查找 O(1)
• 未排序查找未知位置元素 O(n)
• 排序查找未知位置元素 O(logn)

分为两种情况：一种是根据索引去查找元素，一种是查询未知位置的元素；

前者的时间复杂度是 O(1); 后者是 O(n ) 【未排序情况】；如果后者是排序的元素，查找的时间复杂度是 O(logn) ]【排序情况，二分查找】

操作数组的时间复杂度（插入、删除）

数组的插入和删除的效率较低，不过在数组头和数组尾的情况是最好情况，时间复杂度是 O(1)

→ 最好情况下是0(1)的，最坏情况下是O(n)的，平均情况下的时间复杂度是O(n)。

源码分析

根据 成员变量、构造函数、关键方法 三部分来进行分析（jdk 1.8)

成员变量

• DEFAULT_CAPACITY
  • DEFAULT_CAPACITY是ArrayList的默认容量。默认是 10
  • 当使用无参构造函数创建ArrayList实例时，如果第一次添加元素，数组将会被扩展到这个默认大小。
• EMPTY_ELEMENTDATA
  • EMPTY_ELEMENTDATA是用于空实例的共享空数组实例。
  • 使用指定容量构造方法创建ArrayList实例时，内部数组elementData初始化为这个空数组。这种做法是为了优化内存使用，在不需要存储任何元素时不分配内存空间。
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  • 默认大小空实例的共享空数组实例
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA在JDK 1.8中实际上是一样的，都是空数组。
  • 但其语义上用于区分ArrayList是通过无参构造函数创建的还是通过指定初始容量创建的。它标记着ArrayList使用无参构造时的初始状态，当第一次添加元素时，将扩展到DEFAULT_CAPACITY的大小。
• elementData
  • elementData是存储ArrayList元素的数组缓冲区。ArrayList通过这个数组来存储所有的元素。
  • 当元素数量超过这个数组的容量时，ArrayList会创建一个新的数组来替换它，并将旧数组的内容复制到新数组中，从而实现动态扩容。
• size
  • size表示ArrayList中实际存储的元素数量。注意，这个值可能小于elementData的长度，因为elementData的长度代表的是ArrayList的容量，而size才是实际元素的计数。

指定初始容量 → EMPTY_ELEMENTDATA；默认无参构造函数 → DEFAULTCAPACITY_EMPTY_ELEMENTDATA

构造函数

带初始化容量的构造函数

    /**
     * ArrayList 所包含的元素个数
     */
    private int size;

    /**
     * 带初始容量参数的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //如果传入的参数大于0，创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果传入的参数等于0，创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //其他情况，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
    }

无参构造函数，默认创建空集合

    /**
     * 默认无参构造函数
     * DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定集合构造函数

collection 参数构造函数，将 collection 对象转换为数组，然后将数组的地址的值内容赋值给 elementData数组

    /**
     * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
     */
    public ArrayList(Collection<? extends E> c) {
        //将指定集合转换为数组
        elementData = c.toArray();
        //如果elementData数组的长度不为0
        if ((size = elementData.length) != 0) {
            // 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断）
            if (elementData.getClass() != Object[].class)
                //将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 其他情况，用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

关键方法

添加元素

第一次添加数据

• 第一次添加数据的时候会先计算容量，返回 minCapacity
• 判断是否需要扩容，第一次的时候会进行一下扩容
• 10 > 0 ，进行扩容操作
• 然后会获取到第一次初始化数组长度 10 (newCapacity - minCapacity < 0)

第二次至十次添加元素

第十一次添加元素

此时会进行一次扩容，扩容容量为默认容量的 1.5 倍，数据进行数组拷贝到一个新的数组中。

---

常见面试题

相关的一些概念

ArrayList 和 Array 数组 的的区别。

ArrayList 的底层实现是动态数组，支持自动扩容，支持泛型确保类型安全。

而 Array 数组是固定的容量大小，需要在声明的时候就指定固定数据类型和指定大小，支持基本类型和对象。

ArrayList 和 Vector 的区别。

ArrayList 和 Vector 都是 List 接口下的实现类，但是 ArrayList 是线程不安全的，性能较高；

Vector 是线程安全的，是 List 接口的古老实现，但不建议目前使用（同步操作导致性能问题），如果是并发情况下，建议使用 CopyOnWriteArrayList 等.

另外两者的扩容机制不一样，ArrayList 扩容增长为原来的 1.5 倍，Vector 默认增长为原来的 2 倍。

Vector 和 Stack 的区别。

Vector 是 List 接口的古老实现类，是线程安全的有序集合。

Stack 继承于 Vector ，是一个栈结构（后进先出 LIFO）。它提供了栈结构的一些标准操作方法，实现了栈的基本功能。

但是由于同步操作导致性能问题，不推荐目前使用；栈目前一般是使用 Deque 接口的实现类 ArrayDequeu 替代 Stack 。

ArrayList 是否可以添加 null 值。

ArrayList 是可以添加 null 值的，但是不建议；

尽管 ArryayList 支持添加 null ，并且允许 重复添加，但是在使用的过程中代码可能会抛出空指针异常。

见下👇：

在使用包含null值的ArrayList时要特别小心，因为对null的操作可能会导致NullPointerException。

例如，如果你尝试调用null对象的方法或访问其属性，就会遇到这种异常。因此，在处理可能包含null值的ArrayList时，总是好的做法是进行null检查。

ArrayList 插入和删除的时间复杂度。

ArrayList的插入和删除操作的时间复杂度取决于操作的位置：

插入操作：

在 ArrayList 中，末尾添加或者移除元素的时间复杂度都是 O(1)操作，因为不需要移动已有的元素

但是考虑一个情况，就是当插入元素的时候，此时如果数组需要扩容（即当前元素数量已达到数组的容量），则插入的时间复杂度会上升到O(n)，因为需要复制现有的数组到一个更大的数组。

在ArrayList的特定位置插入元素的时间复杂度是O(n)，因为需要将插入点之后的所有元素向后移动一位以腾出空间。这里的n是从插入点到数组末尾的元素数量。

删除操作：

从ArrayList的末尾移除元素通常是O(1)操作，直接删除最后一个元素不需要移动其他元素。

从ArrayList的特定位置删除元素的时间复杂度是O(n)，

ArrayList 的实现原理是什么？ 🚩

• ArrayList 底层是用动态的数组实现的
• ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10
• ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
• ArrayList在添加数据的时候
  • 确保数组已使用长度(size) 加1 之后足够存下下一个数据
  • 计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用 grow 方法扩容（原来的1.5倍）
  • 确保新增的数据有地方存储之后，则将新元素添加到位于 size 的位置上。
  • 返回添加成功布尔值。

---

ArrayList list = new ArrayList(10) 中的 list 扩容几次？

未扩容

如何实现 数组和List 之间的转换 🚩

参考回答：

• 数组转 List， 使用 JDK 中 java.util.Arrays 工具类的 asList 方法
• List 转数组，使用 List 的 toArray 方法，
  • 无参 toArray 方法返回 Object 数组，
  • 传入初始化 长度的数组对象，返回该对象数组

再问：

• 用 Arrays.asList 转 List 后，如果修改了数组内容， list 受影响吗
• List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗

asList 方法的元素指向地址并没有改，如果修改了数组内容， list 内容也会 受影响

toArray 方法是将数据赋值到了一个新的数组中

参考回答：

---

数组 → List

使用Arrays.asList(T... a)方法可以将数组转换为List。

String[] array = {"Apple", "Banana", "Cherry"};
List<String> list = Arrays.asList(array);
// 注意：返回的List为固定大小的List

List → 数组

使用List的toArray()方法可以将List转换为数组。

如果要转换的目标是对象数组，可以直接使用无参的toArray()方法；如果要转换为特定类型的数组，可以使用toArray(T[] a)方法。

//转换为Object数组
List<String> list = Arrays.asList("Apple", "Banana", "Cherry");
Object[] objectArray = list.toArray();

//转换为特定类型的数组
List<String> list = Arrays.asList("Apple", "Banana", "Cherry");
String[] stringArray = list.toArray(new String[0]);
// 注意：toArray(new String[0])中的数组大小通常指定为0，实际返回数组的大小将由List的大小决定

ArrayList 和 LinkedList 的区别是什么？

总结：

• 1、底层数据结构
• 2、效率
• 3、空间
• 4、线程是否安全

---

LinkedList

LinkedList 底层的数据结构是双向链表；非常适合频繁的插入、删除操作（修改指针就行）；查询性能不太好（需要遍历链表查找元素）

LinkedList是Java集合框架中的一部分，实现了List接口和Deque接口，提供了列表和双端队列的功能。

与ArrayList相比，LinkedList在内部采用了双向链表的数据结构。

特点：

• 1、底层实现是双向链表，大小是动态的，可以根据需要增加或减少节点（元素）
• 2、高效的插入和删除，LinkedList可以在任何位置快速插入和删除元素，时间复杂度为O(1)，只要能直接访问到插入或删除的节点。但是，寻找特定位置的节点需要从头节点或尾节点开始遍历，时间复杂度为O(n)。
• 3、支持双向遍历。
• 4、LinkedList的每个元素都是一个节点对象，除了数据外，还包含了两个指针（链接前后节点的），因此相比ArrayList，LinkedList通常会有更高的内存开销。

示例代码：

创建LinkedList并进行基本操作：

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Element 1"); // 添加元素
linkedList.addFirst("Element 0"); // 在头部添加元素
linkedList.addLast("Element 2"); // 在尾部添加元素
linkedList.removeFirst(); // 删除头部元素
linkedList.removeLast(); // 删除尾部元素
String element = linkedList.get(0); // 随机访问，时间复杂度O(n)

关于 LinkedList 支持双向遍历的代码示例说明

在Java的LinkedList类中，双向遍历的支持体现在它实现了List接口和Deque接口。Deque接口提供了在双端队列的两端插入和删除元素的方法，例如：

• 使用addFirst(E e)和addLast(E e)方法在链表的头部或尾部添加元素。
• 使用removeFirst()和removeLast()方法从链表的头部或尾部移除元素。
• 使用getFirst()和getLast()方法获取链表的第一个或最后一个元素。

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

//使用`listIterator()`进行正向遍历`LinkedList`，然后使用相同的迭代器进行反向遍历。
// 正向遍历
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// 反向遍历
while (iterator.hasPrevious()) {
    System.out.println(iterator.previous());
}

---

四、Set

Set 接口的特点有：

• 无序集合，Set接口的实现类通过内部使用映射（Map）来确保元素的唯一性。
• 不允许有重复元素的集合。
• 允许 null的存在但是仅有一个

---

关于 Set 接口下的实现类

• HashSet：
  • 基于HashMap实现，利用HashMap的键来存储Set中的元素，从而保证元素的唯一性。（哈希表）
  • 拥有很好的查找和插入性能，但不保证元素的顺序。
  • 允许使用null元素
• LinkedHashSet：
  • 类似于HashSet，但维护了一个运行于所有条目的双重链接列表，保证了元素的迭代顺序。
  • 继承于 HashSet、又基于LinkedHashMap来实现
  • 底层使用LinkedHashMap来保存所有元素，它继承于HashSet，其所有的方法操作上与HashSet相同
• TreeSet：
  • 基于TreeMap实现，不仅确保元素的唯一性，（红黑树）
  • 可以按照元素的自然顺序或者构造时指定的Comparator进行排序。
• EnumSet
  • 枚举的专用Set。所有的元素都是枚举类型

Set 接口的常用操作

• 添加元素：add(E e)方法用于向集合中添加一个元素。
• 检查元素：contains(Object o)方法用于检查集合中是否存在指定的元素。
• 删除元素：remove(Object o)方法用于删除集合中的指定元素。
• 集合大小：size()方法返回集合中元素的数量。
• 遍历：可以通过迭代器（Iterator）或增强的for循环来遍历Set。

使用场景

• 当需要保持元素唯一性时，如去除重复元素。
• 当元素的顺序不重要时，可以选择HashSet以获得更高的性能。
• 当需要维护元素插入顺序时，LinkedHashSet是一个好的选择。
• 当需要对集合中的元素进行排序时，TreeSet提供了排序的功能。

示例代码：

Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Apple"); // 重复元素，不会被添加
System.out.println(hashSet); // 输出可能是 [Banana, Apple]

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Apple");
linkedHashSet.add("Banana");
System.out.println(linkedHashSet); // 输出 [Apple, Banana], 保持插入顺序

Set<String> treeSet = new TreeSet<>();
treeSet.add("Banana");
treeSet.add("Apple");
System.out.println(treeSet); // 输出 [Apple, Banana], 自然排序

SortedSet

回顾类关系

SortedSet 是 Set 接口的一个扩展，用于保持元素的排序。SortedSet 确保集合中的元素是按照某种特定的顺序排列的，无论是自然排序还是根据提供的 Comparator 进行排序

SortedSet默认的排序顺序是自然顺序，默认的迭代顺序是升序排序，开始是最小的元素，慢慢变大。

Comparator 比较仪，比较标准；对照物

• 主要方法:
  • first(): 返回集合中的第一个（最低）元素。
  • last(): 返回集合中的最后一个（最高）元素。
  • headSet(toElement): 返回此集合中小于 toElement 的元素的视图。
  • tailSet(fromElement): 返回此集合中大于或等于 fromElement 的元素的视图。
  • subSet(fromElement, toElement): 返回集合的一个部分视图，其元素范围从 fromElement（包含）到 toElement（不包含）。
• 特点: 不允许含有重复元素，可以按自然顺序或自定义比较器来排序元素。

TreeSet

• TreeSet 是 SortedSet 接口的一个具体实现，内部使用红黑树（平衡二叉搜索树的一种形式）来管理元素。它保证集合中的元素在任何时间都处于排序状态。
• 主要方法: 作为 SortedSet 的实现，TreeSet 提供了上述 SortedSet 的所有方法。

自然排序操作

使用示例：

import java.util.TreeSet;
import java.util.SortedSet;

public class SetPractice {
    public static void main(String[] args) {
        // 创建一个 TreeSet 实例
        SortedSet<Integer> numbers = new TreeSet<>();

        // 添加元素
        numbers.add(10);
        numbers.add(40);
        numbers.add(30);
        numbers.add(20);
        numbers.add(50);

        // 输出排序后的集合
        System.out.println("SortedSet: " + numbers);

        // 获取并输出第一个元素和最后一个元素
        System.out.println("First: " + numbers.first());
        System.out.println("Last: " + numbers.last());
    }
}

这里默认使用的是自然排序，实际在上面的使用示例中，Integer 对象等一般都会重写 compareTo 方法

实际你去看这个类的时候，会发现它也是实现了 Comparable 接口

public final class Integer extends Number implements Comparable<Integer>

compareTo 方法通常是在实现 Comparable 接口的时候定义的。Comparable 接口是 Java 中的一个通用接口，用于定义对象的自然排序。

再讲几个例子，你可能会更新对此理解更透彻一些。

自然排序操作: 任务管理器：用于管理一系列任务的截止日期，使用 TreeSet 来确保任务按截止日期自然排序

package com.ruoyi.luoqi.collection;
import java.util.*;

/**
 * 任务管理器：用于管理一系列任务的截止日期，使用 TreeSet 来确保任务按截止日期自然排序。
 * 这个类展示了如何使用 TreeSet 处理时间敏感的任务排序。
 * @author luoqi
 * @File TaskManager.java
 * @Desc 任务管理器类，用于演示 TreeSet 的使用。
 * @Create 2024/4/14 9:59
 * @ChangeList
 * --------------------------------------------------------------------
 * Date             Editor          ChangeReason
 * 2024/04/14       luoqi           Initial creation of the file and implementation of task sorting.
 */
public class TaskManager {
    public static void main(String[] args) {
        // 使用 TreeSet 来存储任务的截止日期（使用自然排序）
        SortedSet<Task> tasks = new TreeSet<>();

        // 添加一些任务
        tasks.add(new Task("项目规划", new GregorianCalendar(2024, Calendar.APRIL, 20).getTime()));
        tasks.add(new Task("需求分析", new GregorianCalendar(2024, Calendar.MAY, 15).getTime()));
        tasks.add(new Task("设计阶段", new GregorianCalendar(2024, Calendar.MAY, 30).getTime()));
        tasks.add(new Task("实施阶段", new GregorianCalendar(2024, Calendar.JUNE, 30).getTime()));
        tasks.add(new Task("测试", new GregorianCalendar(2024, Calendar.JULY, 20).getTime()));
        tasks.add(new Task("部署", new GregorianCalendar(2024, Calendar.AUGUST, 10).getTime()));

        // 显示所有任务
        System.out.println("全部任务按截止日期排序：");
        for (Task task : tasks) {
            System.out.println(task);
        }

        // 获取最近的任务
        if (!tasks.isEmpty()) {
            Task firstTask = tasks.first();
            System.out.println("\n最近的任务是: " + firstTask);
        }

        // 查找特定时间前的所有任务
        Date targetDate = new GregorianCalendar(2024, Calendar.JULY, 1).getTime();
        SortedSet<Task> tasksBeforeJuly = tasks.headSet(new Task("", targetDate));
        System.out.println("\n7月1日前的任务：");
        for (Task task : tasksBeforeJuly) {
            System.out.println(task);
        }
    }

    /**
     * Task 类用于存储单个任务的详细信息，如名称和截止日期。
     * 实现 Comparable 接口允许任务根据截止日期进行排序。
     */
    static class Task implements Comparable<Task> {
        String name;
        Date deadline;

        public Task(String name, Date deadline) {
            this.name = name;
            this.deadline = deadline;
        }

        @Override
        public int compareTo(Task other) {
            return this.deadline.compareTo(other.deadline);
        }

        @Override
        public String toString() {
            return name + " - 截止日期: " + deadline;
        }
    }
}

自然排序操作：音乐节演出管理器：用于管理音乐节中乐队的演出时间表。

package com.ruoyi.luoqi.collection;

import java.util.*;

/**
 * 音乐节演出管理器：用于管理音乐节中乐队的演出时间表。
 * 使用 SortedSet 来保证按演出时间自然排序，以便快速检索和管理演出事件。
 * @author luoqi
 * @File MusicFestivalManager.java
 * @Desc 音乐节演出时间表管理类，使用 SortedSet 处理演出时间的排序和检索。
 * @Create 2024/4/14 10:59
 * @ChangeList
 * --------------------------------------------------------------------
 * Date             Editor          ChangeReason
 * 2024/04/14       luoqi           Initial creation and implementation for managing band performances.
 */
public class MusicFestivalManager {
    public static void main(String[] args) {
        // 使用 TreeSet 来存储乐队的演出时间（自然排序）
        SortedSet<Performance> schedule = new TreeSet<>();

        // 添加演出时间
        schedule.add(new Performance("The Beatless", new GregorianCalendar(2024, Calendar.JUNE, 25, 20, 0).getTime()));
        schedule.add(new Performance("Arctic Monkeys", new GregorianCalendar(2024, Calendar.JUNE, 25, 18, 0).getTime()));
        schedule.add(new Performance("Radiohead", new GregorianCalendar(2024, Calendar.JUNE, 25, 22, 0).getTime()));

        // 输出全部演出时间按时间排序
        System.out.println("演出时间表：");
        for (Performance performance : schedule) {
            System.out.println(performance);
        }

        // 获取并输出下一场演出
        if (!schedule.isEmpty()) {
            Performance nextPerformance = schedule.first();
            System.out.println("\n下一场演出是: " + nextPerformance);
        }

        // 查找晚上7点后的所有演出
        Date eveningTime = new GregorianCalendar(2024, Calendar.JUNE, 25, 19, 0).getTime();
        SortedSet<Performance> eveningPerformances = schedule.tailSet(new Performance("", eveningTime));
        System.out.println("\n晚上7点后的演出：");
        for (Performance performance : eveningPerformances) {
            System.out.println(performance);
        }
    }

    /**
     * Performance 类用于存储乐队的名称和演出时间。
     * 实现 Comparable 接口以便按时间进行排序。
     */
    static class Performance implements Comparable<Performance> {
        String bandName;
        Date time;

        public Performance(String bandName, Date time) {
            this.bandName = bandName;
            this.time = time;
        }

        // 按演出时间对演出进行排序
        @Override
        public int compareTo(Performance other) {
            return this.time.compareTo(other.time);
        }

        // 返回演出的字符串表示，包括乐队名称和时间
        @Override
        public String toString() {
            return bandName + " - 演出时间: " + time;
        }
    }
}

自定义比较器

将上面的类 MusicFestivalManager 进行一个基础改造

package com.ruoyi.luoqi.collection;

import java.util.*;

/**
 * 音乐节演出管理器：用于管理音乐节中乐队的演出时间表。
 * 使用 SortedSet 和自定义 Comparator 来保证按演出时间自然排序，以便快速检索和管理演出事件。
 * @author luoqi
 * @File MusicFestivalManager.java
 * @Desc 音乐节演出时间表管理类，使用 SortedSet 和自定义 Comparator 处理演出时间的排序和检索。
 * @Create 2024/4/14 10:59
 * @ChangeList
 * --------------------------------------------------------------------
 * Date             Editor          ChangeReason
 * 2024/04/14       luoqi           Updated to use custom Comparator for sorting performances.
 */
public class MusicFestivalManagerComparator {
    public static void main(String[] args) {
        // 定义自定义比较器
        Comparator<Performance> performanceComparator = new Comparator<Performance>() {
            @Override
            public int compare(Performance p1, Performance p2) {
                return p1.time.compareTo(p2.time);
            }
        };

        // 使用 TreeSet 和自定义比较器来存储乐队的演出时间
        SortedSet<Performance> schedule = new TreeSet<>(performanceComparator);

        // 添加演出时间
        schedule.add(new Performance("The Beatless", new GregorianCalendar(2024, Calendar.JUNE, 25, 20, 0).getTime()));
        schedule.add(new Performance("Arctic Monkeys", new GregorianCalendar(2024, Calendar.JUNE, 25, 18, 0).getTime()));
        schedule.add(new Performance("Radiohead", new GregorianCalendar(2024, Calendar.JUNE, 25, 22, 0).getTime()));

        // 输出全部演出时间按时间排序
        System.out.println("演出时间表：");
        for (Performance performance : schedule) {
            System.out.println(performance);
        }

        // 获取并输出下一场演出
        if (!schedule.isEmpty()) {
            Performance nextPerformance = schedule.first();
            System.out.println("\n下一场演出是: " + nextPerformance);
        }

        // 查找晚上7点后的所有演出
        Date eveningTime = new GregorianCalendar(2024, Calendar.JUNE, 25, 19, 0).getTime();
        SortedSet<Performance> eveningPerformances = schedule.tailSet(new Performance("", eveningTime));
        System.out.println("\n晚上7点后的演出：");
        for (Performance performance : eveningPerformances) {
            System.out.println(performance);
        }
    }

    /**
     * Performance 类用于存储乐队的名称和演出时间。
     */
    static class Performance {
        String bandName;
        Date time;

        public Performance(String bandName, Date time) {
            this.bandName = bandName;
            this.time = time;
        }

        // 返回演出的字符串表示，包括乐队名称和时间
        @Override
        public String toString() {
            return bandName + " - 演出时间: " + time;
        }
    }
}

也许你这样看还不是太明显，继续往下看。

Comparator 的优势

• 可以定义多个不同的比较方法。
• 可以在运行时传入比较器到集合的构造函数。
• 适合那些需要多种排序策略的复杂场景。

自定义比较器：人力资源管理器：用于管理公司员工的列表，并支持根据多种标准对员工进行排序。

package com.ruoyi.luoqi.collection;

import java.util.*;

/**
 * 人力资源管理器：用于管理公司员工的列表，并支持根据多种标准对员工进行排序。
 * 使用自定义 Comparator 和 TreeSet 实现多层次动态排序。
 * @author luoqi
 * @File HumanResourcesManager.java
 * @Desc 人力资源管理系统中的员工排序和管理。
 * @Create 2024/4/14 12:00
 * @ChangeList
 * --------------------------------------------------------------------
 * Date             Editor          ChangeReason
 * 2024/04/14       luoqi           Modified to use custom Comparator for sorting employees in a TreeSet.
 */
public class HumanResourcesManager {
    public static void main(String[] args) {
        // 定义自定义比较器，先按部门排序，部门相同则按姓名排序
        Comparator<Employee> employeeComparator = new Comparator<Employee>() {
            @Override
            public int compare(Employee e1, Employee e2) {
                int departmentComparison = e1.getDepartment().compareTo(e2.getDepartment());
                if (departmentComparison != 0) {
                    return departmentComparison;
                }
                return e1.getName().compareTo(e2.getName());
            }
        };

        // 使用 TreeSet 和自定义比较器来存储员工信息
        SortedSet<Employee> employees = new TreeSet<>(employeeComparator);
        employees.add(new Employee("Alice Johnson", "Accounting", new GregorianCalendar(2019, Calendar.JANUARY, 5).getTime()));
        employees.add(new Employee("Bob Smith", "Marketing", new GregorianCalendar(2021, Calendar.MARCH, 12).getTime()));
        employees.add(new Employee("Charlie Brown", "IT", new GregorianCalendar(2020, Calendar.FEBRUARY, 20).getTime()));
        employees.add(new Employee("David Wilson", "Accounting", new GregorianCalendar(2022, Calendar.APRIL, 25).getTime()));

        // 输出全部员工信息按部门和姓名排序
        System.out.println("Employees sorted by Department and Name:");
        for (Employee employee : employees) {
            System.out.println(employee);
        }
    }

    static class Employee {
        private String name;
        private String department;
        private Date startDate;

        public Employee(String name, String department, Date startDate) {
            this.name = name;
            this.department = department;
            this.startDate = startDate;
        }

        public String getName() { return name; }
        public String getDepartment() { return department; }
        public Date getStartDate() { return startDate; }

        @Override
        public String toString() {
            return String.format("%s, %s Department, Start Date: %s", name, department, startDate);
        }
    }
}

这个是基础的一些用法，当你不需要使用 set 进行去重的话，也可以使用 ArrayList 去进行一些操作

package com.ruoyi.luoqi.collection;

import java.util.*;
/**
 * 人力资源管理器：用于管理公司员工的列表，并支持根据多种标准对员工进行排序。
 * 使用 Comparator 实现多种动态排序策略。
 * @author luoqi
 * @File HumanResourcesManager.java
 * @Desc 人力资源管理系统中的员工排序和管理。
 * @Create 2024/4/14 12:00
 * @ChangeList
 * --------------------------------------------------------------------
 * Date             Editor          ChangeReason
 * 2024/04/14       luoqi           Initial creation and implementation for managing employees.
 */
public class HumanResourcesManagerArrayList {
    public static void main(String[] args) {
        List<Employee> employees = new ArrayList<>();
        employees.add(new Employee("Alice Johnson", "Accounting", new GregorianCalendar(2019, Calendar.JANUARY, 5).getTime()));
        employees.add(new Employee("Bob Smith", "Marketing", new GregorianCalendar(2021, Calendar.MARCH, 12).getTime()));
        employees.add(new Employee("Charlie Brown", "IT", new GregorianCalendar(2020, Calendar.FEBRUARY, 20).getTime()));

        // Comparator for name
        Comparator<Employee> byName = Comparator.comparing(Employee::getName);

        // Comparator for department
        Comparator<Employee> byDepartment = Comparator.comparing(Employee::getDepartment);

        // Comparator for start date
        Comparator<Employee> byStartDate = Comparator.comparing(Employee::getStartDate);

        // Sort by name
        Collections.sort(employees, byName);
        System.out.println("Employees sorted by Name:");
        employees.forEach(System.out::println);

        // Sort by department
        Collections.sort(employees, byDepartment);
        System.out.println("\nEmployees sorted by Department:");
        employees.forEach(System.out::println);

        // Sort by start date
        Collections.sort(employees, byStartDate);
        System.out.println("\nEmployees sorted by Start Date:");
        employees.forEach(System.out::println);
    }

    static class Employee {
        private String name;
        private String department;
        private Date startDate;

        public Employee(String name, String department, Date startDate) {
            this.name = name;
            this.department = department;
            this.startDate = startDate;
        }

        public String getName() { return name; }
        public String getDepartment() { return department; }
        public Date getStartDate() { return startDate; }

        @Override
        public String toString() {
            return String.format("%s, %s Department, Start Date: %s", name, department, startDate);
        }
    }
}

---

五、Queue

Queue接口在Java集合框架中代表了一个先进先出（FIFO）的队列。

Queue继承自Collection接口，提供了队列操作的基本方法，用于在队列的尾部插入元素、从队列的头部检索和移除元素。它主要用于存储待处理元素的集合，特别适合于消息处理和任务调度的场景。

主要方法

• 添加元素：
  • boolean add(E e)：将指定的元素插入此队列的尾部。如果队列已满，抛出一个IllegalStateException。
  • boolean offer(E e)：将指定的元素插入此队列的尾部。如果队列已满，则返回false。
• 检索元素：
  • E element()：检索但不移除此队列的头部。如果队列为空，抛出一个NoSuchElementException。
  • E peek()：检索但不移除此队列的头部。如果队列为空，则返回null。
• 移除元素：
  • E remove()：检索并移除此队列的头部。如果队列为空，抛出一个NoSuchElementException。
  • E poll()：检索并移除此队列的头部。如果队列为空，则返回null。

---

关于 Queue 接口下的实现类：

• LinkedList：
  • 实现了List接口和Queue接口，提供了队列操作的同时，也支持列表操作。作为队列使用时，它是一个双端队列，允许在队列的头部和尾部进行元素插入和移除。
• PriorityQueue：
  • 一个基于优先级堆的无界优先级队列，元素根据其自然顺序或通过构造队列时提供的Comparator来决定顺序。不保证同等优先级元素的顺序。
• ArrayDeque：
  • 既可以作为队列也可以作为栈使用的双端队列。它没有容量限制，内部使用动态数组支持容量的增长
• LinkedBlockingDeque
  • 提供了阻塞操作的能力，非常适合用作生产者-消费者场景

使用场景与示例

Queue接口提供了队列数据结构的标准操作方法，允许按照元素的入队顺序进行处理

示例:

Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
queue.offer("Third");

System.out.println(queue.peek()); // 输出 "First"，队列的头部
System.out.println(queue.poll()); // 移除并输出 "First"
System.out.println(queue.peek()); // 输出 "Second"，现在队列的头部

---

阻塞队列与双端队列

上文讲述了一下关于 Queue 接口的特点及其实现类的使用示例；

如果讲队列按照其行为和功能是能被分为不同的类别，队列主要是分为两大类：

• 阻塞队列（Blocking Queues）
  • 队列满了以后再插入元素则会抛出异常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。
• 双端队列（Deque，即Double Ended Queue）
  • 支持在头、尾两端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

阻塞队列（Blocking Queues）

阻塞队列主要用于生产者-消费者场景，其中队列是生产者和消费者之间共享的资源。

阻塞队列的特点是它在队列为空时，会阻塞（挂起）尝试从队列中取元素的消费者线程；而在队列满时，会阻塞尝试向队列中插入元素的生产者线程。这种队列对于多线程编程非常有用，因为它们帮助协调生产者和消费者之间的速度差异，减少了需要程序员手动实现的同步和协调工作。

实现类：

• ArrayBlockingQueue：一个由数组支持的有界阻塞队列。
• PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。
• LinkedBlockingQueue：一个由链表结构支持的可选有界阻塞队列。

双端队列（Deque）

双端队列是一种特殊的队列，它支持在队列的两端进行插入和移除操作。这种灵活性使得双端队列可以被用作传统的队列和栈两种数据结构。

双端队列既可以是阻塞的，也可以是非阻塞的，取决于具体的实现。

实现类：

• ArrayDeque：一个由动态数组支持的非阻塞双端队列，不支持存储null元素。
• LinkedBlockingDeque：一个由链表结构支持的可选有界阻塞双端队列。
• LinkedList：实现了List和Deque接口的链表结构，支持在列表的两端进行插入和移除操作，但它不是阻塞的。

总结：

阻塞队列的关键特性是它们在某些操作无法立即执行时（例如，队列满时插入或队列空时移除）会阻塞线程，直到操作可以执行。

双端队列提供了从两端操作队列的能力，增加了队列的使用灵活性。它们可以用作传统的FIFO队列或LIFO栈。

在选择队列类型时，应该根据应用场景的需要（如是否需要阻塞操作、是否需要从两端操作队列等）来选择最合适的队列实现。

ArrayDeque 🚩

前文我们已经讲述到：ArrayDeque 既可以作为队列也可以作为栈使用的双端队列。它没有容量限制，内部使用动态数组支持容量的增长。

因此在实际使用的时候，也一般会使用 ArrayDeque 来替代 Stack 栈（Stack 继承 Vector，性能不太好，不建议使用）；

下面是基本介绍：

• 1、ArrayDeque是Java集合框架中的一个类，全名为java.util.ArrayDeque。它实现了Deque接口，提供了双端队列（Double-Ended Queue）的功能。
• 2、与LinkedList相比，ArrayDeque基于动态数组实现，不支持存储null元素。
• 3、ArrayDeque可以作为栈（后进先出，LIFO）或队列（先进先出，FIFO）使用，具有较高的性能和较低的内存开销。

特点：

• 1、底层是动态数组，可自动扩容
• 2、ArrayDeque 不允许插入 null 元素
• 3、双端操作，支持在尾部和头部进行插入和删除操作，既可以作为队列使用，也可以作为栈使用
• 4、线程不安全
  • 高并发情况下建议使用 ConcurrentLinkedDeque 或者 Collections.synchronizedList(new ArrayList<...>()) 以及 BlockingDeque 等。

---

常用方法：

作为Deque的实现，ArrayDeque提供了一系列方法，包括：

• 添加元素：
  • addFirst(E e)和offerFirst(E e)：在队列前端添加元素。
  • addLast(E e)和offerLast(E e)：在队列尾端添加元素。
• 移除元素：
  • removeFirst()和pollFirst()：移除队列前端的元素。
  • removeLast()和pollLast()：移除队列尾端的元素。
• 检查元素：
  • getFirst()和peekFirst()：检查队列前端的元素。
  • getLast()和peekLast()：检查队列尾端的元素。
• 栈操作：（后进先出）
  • push(E e)：将元素压入栈顶（队列前端）。
  • pop()：移除并返回栈顶（队列前端）的元素
  • peek()：返回栈顶元素但不移除。

ArrayDeque由于其高效的性能和灵活的操作，适用于以下场景：

• 作为栈使用：利用push、pop方法实现后进先出的数据结构。
• 作为队列使用：利用offer、poll方法实现先进先出的数据结构。
• 双端队列：需要在两端添加或删除元素的场景

示例代码

Deque<Integer> stack = new ArrayDeque<>();

// 元素入栈
stack.push(1);
stack.push(2);
stack.push(3);

// 访问栈顶元素
System.out.println("栈顶元素: " + stack.peek()); // 输出 3

// 元素出栈
while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}
// 输出：
// 3
// 2
// 1

//作为队列使用演示
Deque<String> deque = new ArrayDeque<>();
deque.offerLast("A"); // 队列尾部添加
deque.offerFirst("B"); // 队列头部添加
System.out.println(deque.pollFirst()); // 输出B，队列头部移除
System.out.println(deque.pollLast()); // 输出A，队列尾部移除

---

BlockingDeque 🐉

在前文讲述到，ArrayDeque 并不是线程安全的，在高并发的情况下，我们也可以考虑使用 BlockingDeque 的实现：比如LinkedBlockingDeque，它提供了阻塞操作的能力，非常适合用作生产者-消费者场景。

基本介绍：

• 1、BlockingDeque是Java并发包（java.util.concurrent）提供的一个接口，它扩展了BlockingQueue接口和Deque接口。
• 2、BlockingDeque是一个线程安全的双端队列，支持阻塞的插入和移除操作。它主要用于生产者-消费者场景，其中元素可以从队列的两端被插入或移除，同时提供了阻塞操作以便在队列满或空时进行等待，直到队列变为可用状态。

特点：

• 1、线程安全
  • BlockingDeque内部通过锁（通常是重入锁）来保证队列的线程安全，使得在多线程环境中插入、移除和访问操作都能够安全执行。
• 2、阻塞操作
  • 提供了阻塞的插入和移除方法。当队列满时，队列会阻塞插入操作的线程；当队列空时，队列会阻塞移除操作的线程，直到队列变为非满或非空状态。
• 3、双端操作
  • 支持在队列的头部和尾部进行插入和移除操作，提供了灵活的数据处理能力。

主要方法

BlockingDeque接口定义了多种方法，包括但不限于：

• 插入方法：
  • addFirst(E e)、addLast(E e)：
    • 在队列的头部或尾部添加元素，如果队列满则抛出IllegalStateException。
  • offerFirst(E e, long timeout, TimeUnit unit)、offerLast(E e, long timeout, TimeUnit unit)：
    • 在队列的头部或尾部添加元素，如果队列满则等待指定的时间，超时返回false。
• 移除方法：
  • removeFirst()、removeLast()：
    • 移除并返回队列头部或尾部的元素，如果队列为空则抛出NoSuchElementException。
  • pollFirst(long timeout, TimeUnit unit)、pollLast(long timeout, TimeUnit unit)：
    • 移除并返回队列头部或尾部的元素，如果队列为空则等待指定的时间，超时返回null。
• 检查方法：
  • getFirst()、getLast()：
    • 检查但不移除队列头部或尾部的元素，如果队列为空则抛出NoSuchElementException。
  • peekFirst()、peekLast()：
    • 检查但不移除队列头部或尾部的元素，如果队列为空则返回null。

实现类

Java并发包提供了BlockingDeque接口的具体实现类，例如：

• LinkedBlockingDeque：
  • 一个基于链表结构的阻塞双端队列。它可选地有界，如果未指定容量，那么它等同于无界，但内存是有限的，因此实际上它还是有界的。
  • LinkedBlockingDeque内部使用一个链表结构来存储元素。这个链表是双向链表，允许在队列的两端进行插入和移除操作。链表的每个节点包含了元素本身以及前后节点的引用，这使得在两端的操作都能高效进行

场景：BlockingDeque非常适合用于生产者-消费者模式，其中生产者和消费者可能在处理速度上有差异。通过阻塞操作，可以在生产者快于消费者时自动进行速度调节，避免资源消耗和溢出，或在消费者快于生产者时等待新元素的产生。

使用示例：

BlockingDeque<String> deque = new LinkedBlockingDeque<>();

// 生产者线程
new Thread(() -> {
    try {
        deque.putFirst("1");
        deque.putLast("2");
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}).start();

// 消费者线程
new Thread(() -> {
    try {
        System.out.println(deque.takeFirst()); // 等待并获取队列头部元素
        System.out.println(deque.takeLast()); // 等待并获取队列尾部元素
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}).start();

---

PriorityQueue

PriorityQueue 是 Queue接口 下的一个实现类，是实现优先队列的一个理想选择；

介绍：

• 1、PriorityQueue 按照元素的自然排序或者构造队列时指定的Comparator进行排序，确保队列头部始终是最小（或根据Comparator定义的其他顺序）的元素
• 2、PriorityQueue是实现优先队列的理想选择，优先队列允许高优先级的元素先于低优先级的元素被处理
• 3、PriorityQueue提供了一种方便的方式来处理需要根据优先级排序的元素集合，它通过堆数据结构实现，保证了高效的元素插入和移除操作。

特点：

• 1、元素排序
• 2、线程不安全
• 3、不允许插入 null 值
• 4、快速访问最小元素
  • 访问最小元素（或根据Comparator定义的顺序中的"最小"元素）的时间复杂度是O(1)，但移除该元素或插入任意新元素的时间复杂度通常是O(log n)。
• 5、底层实现是二叉堆（Binary Heap）

---

场景：

• 任务调度：在需要根据优先级处理任务时，如操作系统中的任务调度。
• 数据流处理：在数据流中实时地找到最小（或最大）元素，如求一系列数据中的中位数或其他统计值

注意事项：

• 使用PriorityQueue时，确保其元素实现了Comparable接口或者在构造PriorityQueue时提供了一个Comparator，否则会在运行时抛出ClassCastException。
• PriorityQueue的迭代器不保证以排序的顺序遍历元素。如果需要有序遍历，可以考虑先将PriorityQueue转换为数组或列表，并对其排序。
• 虽然PriorityQueue提供了快速访问最小元素的能力，但它并不支持随机访问，即不能直接通过索引来访问元素。

使用示例：

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(20);
pq.add(15);

// 访问队列头部元素（最小元素），输出：10
System.out.println(pq.peek());

// 移除并返回队列头部元素，输出：10
System.out.println(pq.poll());

// 此时队列头部元素变为15
System.out.println(pq.peek());

---

六、Map

Map 接口是我们使用频率非常高的一个集合，它与单列集合不同的是，它是基于键值对的一个结构；

特点：

• 1、由一系列键值对组成的集合，提供了key到Value的映射。同时它没有继承Collection；
• 2、它保证了key与value之间的一一对应关系，一个key对应一个value；通过键可以快速查找、更新或删除对应的值
• 3、键不能重复，value值可以相同。

主要方法

Map接口提供了多种操作映射的方法，包括：

• put(K key, V value)：将指定的值与此映射中的指定键关联（可选操作）。
• get(Object key)：返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回null。
• remove(Object key)：如果存在该键的映射关系，则将其从映射中移除（可选操作）。
• containsKey(Object key)：如果此映射包含指定键的映射关系，则返回true。
• containsValue(Object value)：如果此映射将一个或多个键映射到指定值，则返回true。
• keySet()：返回此映射中包含的键的Set视图。
• values()：返回此映射中包含的值的Collection视图。
• entrySet()：返回此映射中包含的映射关系的Set视图。

主要实现类

• HashMap：基于哈希表的Map接口的非同步实现，允许使用null作为键和值，不保证映射的顺序。
• LinkedHashMap：HashMap的一个子类，保持了映射的插入顺序或最后访问顺序。
• TreeMap：基于红黑树的NavigableMap实现。映射按照键的自然顺序（使用Comparable）或构造时提供的Comparator进行排序。
• Hashtable：是一种旧的、同步的键值对集合，它与HashMap类似，但不允许null键和null值。由于其同步特性，通常建议在需要线程安全的场景中使用ConcurrentHashMap代替Hashtable。

相关集合

集合	是否线程安全	底层实现	是否支持null key	是否支持null value	默认初始容量	扩容机制
HashMap (JDK1.8+)	否	数组 + 链表/红黑树	是 (限1个)	是	16	当容量>75%时，容量翻倍
Hashtable	是	数组 + 链表	否	否	11	容量翻倍 + 1
TreeMap	否	红黑树	否	是	-	-
LinkedHashMap	否	数组 + 链表/红黑树 + 双向链表	是 (限1个)	是	16	当容量>75%时，容量翻倍
WeakHashMap	否	数组 + 链表	是 (限1个)	是	16	当容量>75%时，容量翻倍
IdentityHashMap	否	数组	是 (限1个)	是	32	容量翻倍
EnumMap	否	数组	否	是	-	根据枚举键的数量确定
ConcurrentHashMap (JDK1.7)	是	分段锁	否	是	16	当段的某个容量>75%时，该段容量翻倍
ConcurrentHashMap (JDK1.8+)	是	数组 + 链表/红黑树	否	是	16	当容量>75%时，容量翻倍

HashMap 🚩

HashMap 的 Map 接口下非常核心的一个类，它主要用来存放键值对，基于哈希表实现

它非常适用需要快速访问、插入和删除键值对的场景，特别是当不关心元素顺序时。

由于它不是线程安全的，在多线程环境下需要外部同步或使用ConcurrentHashMap。

基本介绍

• 1、HashMap是Java集合框架中非常核心的一个类，它实现了Map接口，提供了键值存储的映射功能，其中键是唯一的。
• 2、HashMap允许使用null值和null键，且不保证映射的顺序（它不保证顺序会随着时间的推移保持不变）。

特点：

• 【键唯一，不保证顺序，允许空值】
• 2、默认初始容量：HashMap的默认初始容量是16。
• 3、加载因子和扩容：
  • 加载因子默认为0.75，它是容量和阈值的比值。
  • 当HashMap中的条目数超过容量与加载因子的乘积时，HashMap会进行扩容，即创建一个新的数组来存储元素，并重新计算每个元素的位置。新数组的容量是原数组的两倍。

时间复杂度

插入和查找：在理想情况下（哈希函数良好且键均匀分布），HashMap的get和put操作的时间复杂度可以是O(1)。但在最坏的情况下（所有键都映射到同一个桶），时间复杂度会退化到O(n)。通过JDK1.8的优化（引入红黑树），即使在哈希冲突较多的情况下，性能也得到了显著提升。

底层实现

• 1、在JDK1.8之前
  • HashMap主要通过数组+链表的方式实现。
  • 数组被用作主要的数据结构来存储元素，而链表则用于解决哈希冲突（两个或多个键的哈希值相同）。
  • 当多个元素被映射到同一个桶（数组的同一个位置）时，这些元素以链表的形式存储。
• 2、从JDK1.8开始，
  • HashMap的实现引入了红黑树。当链表的长度超过一定阈值（默认为8）时，链表将转换成红黑树，以减少搜索时间。
  • 相反，当红黑树中的节点数少于阈值时（一旦红黑树的实际节点数降到少于6个时），红黑树会转换回链表。这种结构的引入显著提高了HashMap在高哈希冲突情况下的性能。
  • 如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树【红黑树的维护成本（比如保持平衡）可能导致性能下降，因此当链表的长度超过一定阈值，也会先要求数组长度超过 64 再考虑转换红黑树】

源码分析

常见属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final float DEFAULT_LOAD_FACTOR = 0.75f;

transient Node<K,V>[] table;

transient int size;

添加数据

• HashMap 是惰性加载，在创建对象时并没有初始化数组
• 在无参的构造函数中，设置了默认的加载因子是 0.75

添加数据流程图

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict) {  
    Node<K,V>[] tab; Node<K,V> p; int n, i;  
    //判断数组是否未初始化
    if ((tab = table) == null || (n = tab.length) == 0)  
	    //如果未初始化，调用 resize 方法，进行初始化
        n = (tab = resize()).length;  
	//通过 & 运算求出该数据(key)的数组下标并判断该下标位置是否有数据
    if ((p = tab[i = (n - 1) & hash]) == null)  
	    //如果没有，直接将数据放在该下标位置
        tab[i] = newNode(hash, key, value, null);  
	//该数组下标有数据的情况
    else {  
        Node<K,V> e; K k;  
        //判断该位置的 key 和新来的数据是否一样
        if (p.hash == hash &&  
            ((k = p.key) == key || (key != null && key.equals(k))))  
            //如果一样，证明为修改操作，该节点的数据赋值给 e，后边会用到
            e = p;  
		//判断是不是红黑树
        else if (p instanceof TreeNode)  
	        //如果是红黑树的话，进行红黑树的操作
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
		//新数据和当前数组既不相同，也不是红黑树节点，证明是链表
        else {  
	        //遍历链表
            for (int binCount = 0; ; ++binCount) {  
	            //判断 next 节点，如果为空的话，证明遍历到链表尾部了
                if ((e = p.next) == null) {  
	                //将新增放入到链表尾部
                    p.next = newNode(hash, key, value, null);  
                    //因为新插入了一条数据，判断链表长度是不是大于等于8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
	                    //如果是，进行转换红黑树操作
                        treeifyBin(tab, hash);  
                    break;  
                }  
                //判断链表当中有数据相同的值，如果一样，证明为修改
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  
				//把下一个节点赋值为当前节点
                p = e;  
            }  
        }  
        //判断 e 是否为空(e 值为修改操作存放原数据的变量)
        if (e != null) { // existing mapping for key  
	        //不为空的话证明是修改操作，取出老值
            V oldValue = e.value;  
            //onlyIfAbsent 传过来的是 false（因此这里一定会执行）
            if (!onlyIfAbsent || oldValue == null)  
	            //将新值赋值给当前节点
                e.value = value;  
            afterNodeAccess(e);  
            //返回老值
            return oldValue;  
        }  
    } 
    //计数器，计算当前节点的修改次数 
    ++modCount;  
    if (++size > threshold)  
	    //进行扩容操作
        resize();  
	//空方法
    afterNodeInsertion(evict);  
    //添加操作时，返回空值
    return null;  
}

总结：

HashMapl的put方法的具体流程

• 1.判断键值对数组table是否为空或为null,否则执行resize0进行扩容（初始化）
• 2.根据键值key计算hash值得到数组索引
• 3.判断table[i]== null,条件成立，直接新建节点添加
• 4.如果table[0]== null,不成立
  • 4.1 判断table[i] 的首个元素是否和 key一样，如果相同直接覆盖value
  • 4.2 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
  • 4.3 遍历 table[i] ，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现 key 已经存在直接覆盖value
• 5.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold(数组长度 * 0.75)，如果超过，进行扩容。

扩容机制

后续优化一下，有相关源码的一个解析： https://www.bilibili.com/video/BV1yT411H7YK/?p=82&spm_id_from=pageDriver&vd_source=6a019ecccfe7d8f62b9a3fe99c723bd0

有部分资料还提供 hashmap 相关的一个演示过程，跳过

总结

讲一讲 HashMap 的扩容机制

• 1、在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）
• 2、每次扩容的时候，都是扩容之前容量的2倍
• 3、扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
  • 没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置
  • 如果是红黑树，走红黑树的添加
  • 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash&oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

常见面试题 🚩

说一下 HashMap 的实现原理。

追问：HashMap 的 JDK 1.7 和 JDK 1.8 有什么区别？

总结上面两题：

1.说一下HashMap的实现原理？

• 1、底层使用hash表数据结构，即数组+（链表|红黑树）
• 2、添加数据时，计算 key 的值确定元素在数组中的下标
  • key相同则替换
  • 不同则存入链表或红黑树中
• 获取数据通过key的hash计算数组下标获取元素

2.HashMap的jdk1.7和jdk1.8有什么区别

• JDK1.8之前采用的拉链法，数组+链表
• JDK1.8之后采用数组+链表+红黑树，链表长度大于8且数组长度大于64则会从链表转化为红黑树

HashMapl的put方法的具体流程

• 1.判断键值对数组table是否为空或为null,否则执行resize0进行扩容（初始化）
• 2.根据键值key计算hash值得到数组索引
• 3.判断table[i]== null,条件成立，直接新建节点添加
• 4.如果table[0]== null,不成立
  • 4.1 判断table[i] 的首个元素是否和 key一样，如果相同直接覆盖value
  • 4.2 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
  • 4.3 遍历 table[i] ，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现 key 已经存在直接覆盖value
• 5.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold(数组长度 * 0.75)，如果超过，进行扩容。

讲一讲 HashMap 的扩容机制

• 1、在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）
• 2、每次扩容的时候，都是扩容之前容量的2倍
• 3、扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
  • 没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置
  • 如果是红黑树，走红黑树的添加
  • 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash&oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

讲一下 HashMap 中的寻址算法

• 1、计算对象的hashCode()
• 2、再进行调用 hash()方法 进行二次哈希，hashcode值右移16位再异或运算，让哈希分布更为均匀
• 3、最后(capacity-1)&hash得到索引

为何 HashMap 的数组长度一定是 2 的次幂？

• 计算索引时效率更高：如果是2的次幂可以使用位与运算代替取模
• 扩容时重新计算索引效率更高：hash&QldCap == 0 的元素留在原来位置，否则新位置=旧位置+oldCap

这里待确认一下 to be contined...

HashMap 在1.7 情况下的多线程死循环问题

后面再看了 to be contined....

---

ConcurrentHashMap 🚩

高并发情况键值对集合一般会考虑使用 ConcurrentHashMap；

基本介绍

• 1、ConcurrentHashMap是Java中支持高并发、线程安全的哈希表实现，它是在java.util.concurrent包中提供的。
• 2、在并发情况下提供了更高的读写性能
  • 与Hashtable和同步的HashMap（通过Collections.synchronizedMap方法包装得到）相比，ConcurrentHashMap在并发环境下提供了更高的读写性能

基本特点

• 1、线程安全： ConcurrentHashMap内部采用特定的同步策略来保证多线程环境下的线程安全，而不是简单地对所有方法进行同步处理。
• 2、高并发性能： 通过减少锁的竞争，ConcurrentHashMap允许多个线程同时读写不同段的数据，从而提高并发性能。
• 3、不允许null键和null值
  • 与HashMap不同，ConcurrentHashMap不允许使用null键或null值，这是为了避免在并发环境下的歧义和错误

底层实现

JDK 1.7

在JDK 1.7及之前的版本中，ConcurrentHashMap采用分段锁机制：

• 分段锁（Segmentation）：整个ConcurrentHashMap被分为若干段（Segment），每一段是一个独立的HashMap，并且拥有自己的锁。当线程访问某一段的数据时，只需要获取这一段的锁，而对其他段的数据的读写操作可以并发进行，从而实现更高的并发度。
• 锁粒度：与对整个数据结构加锁相比，分段锁大大减小了锁的粒度，提高了并发访问时的性能，但同时也增加了内存开销。

JDK 1.8

在JDK 1.8中，ConcurrentHashMap的实现被彻底重写，以实现更高的并发性能：

• CAS操作和synchronized：JDK 1.8中的ConcurrentHashMap使用了一种不同的同步策略，它放弃了分段锁，转而使用了更细粒度的同步机制。通过使用CAS（Compare-And-Swap）操作来支持无锁的更新，对于需要加锁的场景，则使用内部锁（synchronized）来保证线程安全。
• 节点锁：在结构变化（如节点添加或删除）时，ConcurrentHashMap通过对节点对象加锁来实现线程安全的更新。
• 树化：和HashMap类似，当链表过长时，ConcurrentHashMap会将链表转换为红黑树，以提高搜索效率。

使用示例：

//`ConcurrentHashMap`通过高效的并发控制机制，在保证线程安全的同时，提供了高并发性能，是Java并发编程中不可或缺的数据结构。
//展示如何创建一个`ConcurrentHashMap`，向其中添加一些键值对，以及如何安全地进行读写操作
import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        // 创建一个ConcurrentHashMap实例
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

        // 向ConcurrentHashMap中添加一些键值对
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        // 使用lambda表达式来计算键的值（如果键不存在，则初始化；否则，增加其值）
        map.compute("one", (key, value) -> (value == null) ? 1 : value + 1);
        map.compute("four", (key, value) -> (value == null) ? 1 : value + 1);

        // 遍历并打印ConcurrentHashMap中的所有键值对
        map.forEach((key, value) -> System.out.println(key + " => " + value));

        // 获取并打印一个特定的值
        Integer value = map.get("two");
        System.out.println("Value for 'two': " + value);

        // 使用并行操作来转换ConcurrentHashMap中的所有值
        map.replaceAll((key, oldValue) -> oldValue * 10);
        System.out.println("After replaceAll operation:");
        map.forEach((key, newValue) -> System.out.println(key + " => " + newValue));
    }
}

---

LinkedHashMap

LinkedHashMap是Java集合框架中的一部分，它是HashMap的一个子类，底层基于HashMap实现，但同时使用了一个双向链表来维护元素的插入顺序或访问顺序。

基本介绍与特点

• 1、基于哈希表实现，用于存储键值对（LinkedHashMap继承自HashMap）；支持快速的查找、插入和删除操作。
• 2、LinkedHashMap内部维护了一个双向链表来记录所有的键值对。
  • 双向链表中的每个节点包含了键、值、指向前一个节点的引用和指向后一个节点的引用。
• 3、默认情况下，LinkedHashMap按照元素的插入顺序保存这些元素。
  • 如果在构造函数中设置了accessOrder为true，则会按照访问顺序（最近最少使用顺序）来保存元素。
• 4、由于使用了双向链表，LinkedHashMap在维护插入顺序方面需要额外的内存。
  • 查找元素的性能与HashMap相似，因为底层都是基于哈希表实现的。
  • 在迭代整个集合时，LinkedHashMap比普通的HashMap效率更高，因为它通过链表顺序访问元素，而不是哈希表的桶位顺序。

总结：LinkedHashMap是HashMap和双向链表结构的结合，这使得它既具有哈希表的高效键值对存取特性，又能保持键值对的顺序。

使用示例：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // 创建一个LinkedHashMap
        Map<String, String> linkedHashMap = new LinkedHashMap<>();

        // 向LinkedHashMap中添加一些键值对
        linkedHashMap.put("one", "Java");
        linkedHashMap.put("two", "Python");
        linkedHashMap.put("three", "C++");

        // 按插入顺序遍历LinkedHashMap
        System.out.println("Iterating over LinkedHashMap:");
        for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }

        // 创建一个按访问顺序（LRU顺序）的LinkedHashMap
        Map<String, String> accessOrderLinkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderLinkedHashMap.put("one", "Java");
        accessOrderLinkedHashMap.put("two", "Python");
        accessOrderLinkedHashMap.put("three", "C++");

        // 模拟访问
        accessOrderLinkedHashMap.get("one");
        accessOrderLinkedHashMap.get("two");

        // 再次遍历，观察访问顺序
        System.out.println("\nIterating over access-order LinkedHashMap:");
        for (Map.Entry<String, String> entry : accessOrderLinkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

---

七、并发集合

Java 的 java.util.concurrent包提供了多个线程安全的集合类，如 ConcurrentHashMap、CopyOnWriteArrayList等。

是否推荐使用 Collections.synchronizedList方法

Collections.synchronizedList方法提供了一种快捷的方式来将任何列表包装成线程安全的列表。

这个方法通过在每个方法调用上添加同步锁（即在方法上加上synchronized关键字）来实现线程安全。

尽管这种方式可以在多线程环境中保护列表免受并发修改的影响，但它并不总是被推荐使用（它的性能开销和限制使得它不适合所有场景）

在实际应用中，根据具体需求选择专门设计用于并发环境的集合类，往往能够提供更好的性能和更强的功能。

CopyOnWriteArrayList

CopyOnWriteArrayList是Java并发包（java.util.concurrent）中提供的一个线程安全的List实现。

它是ArrayList的一个线程安全变体，使用写时复制（copy-on-write）策略来保证集合的一致性和线程安全，而不是通过锁来同步访问。

写时复制策略

写时复制是一种用于优化多线程环境下读操作远多于写操作的场景的策略。它的工作原理如下：

• 读操作：可以直接读取内部数组，不需要加锁，因为内部数组不会改变，这使得读操作非常高效。
• 写操作（如添加、删除、修改元素）：不直接在当前数组上修改，而是先复制一份当前数组，然后在这个副本上进行修改。修改完成后，将内部引用切换到这个已修改的副本。这个过程需要加锁，以确保副本的创建、修改和引用切换的原子性。

主要特性

• 线程安全：通过写时复制策略，CopyOnWriteArrayList提供了线程安全的List操作，无需外部同步。
• 高并发性能：读操作无锁，大大提高了并发读的性能，特别适合读多写少的场景。
• 迭代器强一致性：迭代器反映的是列表在迭代器创建时的状态，不会感知到迭代器创建后的修改。因此，迭代器不会抛出ConcurrentModificationException异常。

使用场景

CopyOnWriteArrayList适用于读操作远多于写操作的并发场景，如事件监听器列表、缓存等。

注意事项：

• 内存消耗：每次写操作都会复制整个底层数组，因此在元素数量较多或元素本身较大时，写操作会消耗较多内存和时间。
• 写操作成本：由于复制整个数组的需要，写操作（添加、删除、修改）比标准的ArrayList慢，特别是对于大型列表。

CopyOnWriteArrayList在迭代过程中对列表进行修改是安全的，迭代器不会抛出ConcurrentModificationException，它操作的是数组的一个快照。

使用示例：

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListExample {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");

        // 使用迭代器遍历列表
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
            // 迭代过程中修改列表，不会影响到迭代器
            list.add("JavaScript");
        }
        // 迭代器完成后，列表包含新添加的元素
        System.out.println(list);
    }
}

---

八、数据结构

链表

单向链表

链表中的某个节点为 B ， B 的下一个节点为 C ；表示：B.next == C

查询操作

• 只有在查看头节点的时候不需要遍历链表，时间复杂度是 O(1)
• 查询其他节点需要遍历链表，时间复杂度是 O(n)

插入/删除操作

双向链表

时间复杂度分析：

常见面试题

单向链表和双向链表的区别是什么？

• 单向链表只有一个方向，结点只有一个后继指针 next。
• 双向链表它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 pre 指向前面的结点

链表操作数据的时间复杂度是多少？

• 单向链表
  • 查询：头O(1)，其他 O(n)
  • 插入/删除：头O(1)，其他 O(n)
• 双向链表
  • 查询：头尾 O(1); 其他 O(n)；给定结点 O(1)
  • 插入/删除：头尾 O(1); 其他 O(n)；给定结点 O(1)

树

二叉树

Java 中有两个方式实现二叉树：数组存储，链式存储

基于链式存储

在二叉树中，比较常见的二叉树有：

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 红黑树

满二叉树

略

完全二叉树

略

二叉搜索树

二叉搜索树（Binary Search Tree, BST）又名：二叉查找树，有序二叉树或者排序二叉树

树中的任意一个节点，其左子树的每个节点的值，都要小于这个节点的值，而右子树节点的值都要大于这个节点的值。

一般情况下，二叉搜索树的插入、查询、删除的时间复杂度是 O(logn)

极端情况

极端情况下会出现单链表的情况，此时查询的时间复杂度是O(n)

总结，面试题

什么是二叉树

• 1、每个节点最多有两个“叉”，分别是左子节点和右子节点
• 2、不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右字节点
• 3、二叉树每个节点的左子树和右子树也分别能满足二叉树的定义

什么是二叉搜索树

• 二叉搜索树(Binary Search Tree,BST）又名二叉查找树，有序二叉树
• 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值而右子树节点的值都大于这个节点的值
• 没有键值相等的节点·
• 通常情况下二叉树搜索的时间复杂度为O(ogn)

红黑树

二叉树 → 二叉搜索树 → 红黑树

红黑树：自平衡二叉搜索树

红黑树是一种自平衡的二叉搜索树（BST），在1980年由Leonidas J. Guibas和Robert Sedgewick提出。它能够确保任何一个节点的左右子树的高度差不会超过最短子树的二倍。因此，红黑树是相对平衡的，这种特性使得它在插入、删除、查找操作中都能保持较高的性能，最坏情况下也能保证这些操作的时间复杂度为O(log n)。

红黑树的性质如下：

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点，空节点）是黑色的。
4. 每个红色节点的两个子节点都是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树的操作：

• 插入：插入新节点时，默认节点为红色，以保持性质5。如果违反了红黑树的性质，就通过旋转和重新着色的方式来修正。
• 删除：删除节点可能会破坏红黑树的性质，同样需要通过旋转和重新着色来恢复性质。
• 查找：查找操作与普通的二叉搜索树相同，沿树向下进行，直到找到目标节点或到达叶子节点。

时间复杂度：

红黑树的时间复杂度主要体现在其基本操作上：查找（搜索）、插入和删除。由于红黑树是一种自平衡的二叉搜索树，它能够保证在最坏的情况下这些操作的时间复杂度为O(log n)，其中n是树中节点的数量。下面是对每种操作复杂度的具体说明：

• 查找（搜索）
  • 时间复杂度：O(log n)
  • 解释：查找操作与普通二叉搜索树一样，从根节点开始，逐级向下比较，直到找到目标节点或达到叶子节点（NIL节点）。由于红黑树保持了良好的平衡性，其高度大约为log n，所以查找的最坏情况时间复杂度为O(log n)。
• 插入
  • 时间复杂度：O(log n)
  • 解释：插入操作首先是在二叉搜索树中插入节点，这部分的时间复杂度是O(log n)。插入后可能会违反红黑树的性质，需要通过一系列的旋转和重新着色来修复，但这些操作的时间复杂度是常数级的，因此插入操作的总体时间复杂度仍然是O(log n)。
• 删除
  • 时间复杂度：O(log n)
  • 解释：删除操作较为复杂，因为删除节点后可能会破坏红黑树的性质。删除操作分为两步：首先是在二叉搜索树中删除节点，然后通过旋转和重新着色来修复可能违反的红黑树性质。与插入操作类似，由于修复操作的复杂度是常数级的，删除操作的总体时间复杂度也是O(log n)。

---

保证平衡

红黑树的复杂度

• 查找 O(logn)
• 添加 O(logn)
• 删除 O(logn)

---

总结：

什么是红黑树

• 红黑树(Red Black Tree):也是一种自平衡的二叉搜索树(BST)
• 所有的红黑规则都是希望红黑树能够保证平衡
• 红黑树的时间复杂度：查找、添加、删除都是Ologn)

散列表

基础概念

散列表(Hash Table)又名哈希表/Hash表，是根据键(Key)直接访问在内存存储位置值(Value)的数据结构，它是 由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

散列函数

将键(key)映射为数组下标的函数叫做散列函数。可以表示为：hashValue=hash(key)

散列函数的基本要求：

• 散列函数计算得到的散列值必须是大于等于O的正整数，因为hashValue需要作为数组的下标。
• 如果key1 == key2,那么经过hash后得到的哈希值也必相同即：hash(key1) == hash(key2)
• 如果key1 != key2,那么经过hash后得到的哈希值也必不相同即：hash(key1) != hash(key2)

散列冲突

散列冲突（Hash Collision）发生在不同的输入值经过散列函数处理后得到相同的散列值。

实际的情况下想找一个散列函数能够做到对于不同的 key 计算得到的散列值都不同几乎是不可能的，即便像著名的 MD5,SHA等哈希算法也无法避免这一情况，这就是散列冲突（或者哈希冲突，哈希碰撞，就是指多个key映射到同一个数组下标位置)

---

解决哈希冲突的主要方法有下面几种：

• 开放寻址法（Open Addressing）
• 链地址法（Separate Chaining）
• 再散列（Rehashing）
• ....

回答的时候可以就讲一下链地址法

这种方法就是数组 + 链表的解决方式 👇

散列冲突-链表法（拉链）

链地址法是将所有散列值相同的元素存储在同一个位置，但是这个位置不直接存储元素，而是存储一个指向元素链表（或其他动态数据结构，如树）的指针。散列到同一位置的所有元素都将被添加到这个链表中。

链地址法的优点是简单、直观，链表中的元素可以无限增加，解决了散列表的扩容问题，且删除和添加操作简单。但是链表过长会导致查找效率降低。

• (1)插入操作，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是O(1)
• (2)当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除
  • 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)
    • 平均情况下的时间复杂度是O(1)：当散列表的装载因子适中，且散列函数分布均匀时，每个槽对应的链表长度会比较短，这意味着查找或删除操作中遍历链表的步骤平均只需要常数时间，所以平均情况下的时间复杂度接近O(1)。
  • 散列表可能会退化为链表，查询的时间复杂度就从O(1)退化为O(n)
    • 最坏情况下退化为O(n)：如果散列表中的所有元素都散列到同一个槽中，那么这个槽对应的链表就包含了所有元素，散列表就退化为了普通的链表。在这种情况下，查找或删除一个元素的时间复杂度会退化为O(n)，其中n是散列表中元素的总数。
  • 将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是O(log)
    • 使用高效的动态数据结构优化：为了避免散列表在极端情况下退化，可以将链地址法中的链表改造为其他高效的动态数据结构，比如红黑树。红黑树是一种自平衡的二叉搜索树，它可以保证在最坏情况下的查找、插入和删除操作的时间复杂度为O(log n)，其中n是树中元素的数量。因此，如果将链表改造为红黑树，即使在最坏的情况下，查找操作的时间复杂度也可以从O(n)优化到O(log n)。

将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止 DDos攻击

---

总结：

1.什么是散列表？

• 散列表(Hash Table)又名哈希表/Hash表
• 根据键(Key)直接访问在内存存储位置值(Value)的数据结构
• 由数组演化而来的，利用了数组支持按照下标进行随机访问数据

2.散列冲突

• 散列冲突又称哈希冲突，哈希碰撞
• 指多个key映射到同一个数组下标位置

3.散列冲突-链表法（拉链）

• 数组的每个下标位置称之为桶(bucket)或者槽(slot)
• 每个桶（槽)会对应一条链表
• hash冲突后的元素都放到相同槽位对应的链表中或红黑树中

---

附录

集合接口的操作特性

Map 接口相关的一些实现类特点

• HashMap（JDK1.8及以上）
  • 基于哈希表的Map接口的非同步实现
  • 允许使用 null 值和 null 键
  • 数据结构可以看成数组+链表+红黑树
  • 采用了Fail- Fast机制
• Hashtable
  • 基于哈希表的Map接口的同步实现, 使用synchronized实现线程安全
  • 不允许使用null值和null键
  • 底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体
• ConcurrentHashMap（JDK1.7版本）
  • 采用数组+分段锁的方式实现
  • 数据结构：Segment 数组 + HashEntry 数组 + 链表
• ConcurrentHashMap（JDK1.8版本）
  • 数据结构：Node 数组 + 链表 / 红黑树。
  • 当冲突链表达到一定长度时，链表会转换成红黑树。
• TreeMap
  • 实现了SortedMap接口，键以某种排序规则排序
  • 内部以red-black（红-黑）树数据结构实现
• LinkedHashMap
  • 继承于HashMap
  • 非同步，允许使用null值和null键
  • 底层使用哈希表和双向链表来保存所有元素
• WeakHashMap
  • 支持null值和null键，fast-fail机制，不允许重复
  • key只保留对实际对象的弱引用，当key所引用的对象没有被其他强引用变量所引用，则这些key所引用的对象可能被垃圾回收，WeakHashMap也可能自动删除这些key所对应的key-value对。
• IdentifyHashMap
  • 在IdentityHashMap中，当且仅当两个key严格相等（key1== key2）时，IdentityHashMap才认为两个key相等；相对于普通HashMap而言，只要key1和key2通过equals()方法返回true，且它们的hashCode值相等即可。
• EnumMap
  • EnumMap是一个与枚举类一起使用的Map实现，EnumMap中的所有key都必须是单个枚举类的枚举值。创建EnumMap时必须显示或隐式的指定它对应的枚举类。

---

参考

• https://javaguide.cn/java/collection/java-collection-questions-01.html
• https://javaguide.cn/java/collection/java-collection-questions-02.html#map-重要
• https://www.54benniao.com/a/ptarer.html